package common;

import java.util.ArrayList;
import java.util.List;

public class Utils {
    public static void main(String[] args) {
        binarySons(7);
    }

    //x 和 y 的最大公约数
    private static int gcd(int x, int y){
        while (x != 0){
            int tmp = x;
            x = y % x;
            y = tmp;
        }
        return y;
    }

    //x 和 y 的最大公倍数
    private static int lcm(int x, int y){
        return x * y / (gcd(x, y));
    }

    //状态压缩枚举子集
    private static void binarySons(int n){
        for (int i = n, bit = n; i > 0; i = (i - 1) & bit){
            System.out.println(i);
        }
    }

    //质数判断
    private static boolean isZhi(int n){
        int i = 2;
        while (i * i <= n){
            if (n % i == 0){
                return false;
            }
            i++;
        }
        return true;
    }

    //二分找左
    private static int smaller(int[] arr, int goal){
        int l = 0, r = arr.length - 1;
        while (l < r){
            int m = (l + r + 1) >>> 1;
            if (arr[m] > goal){
                r = m - 1;
            }else {
                l = m;
            }
        }
        if(arr[l] > goal){
            return -1;
        }
        return l;
    }

    //二分找右
    private static int bigger(int[] arr, int goal){
        int l = 0, r = arr.length - 1;
        while (l < r){
            int m = (l + r) >>> 1;
            if (arr[m] < goal){
                l = m + 1;
            }else {
                r = m;
            }
        }
        if(arr[l] < goal){
            return -1;
        }
        return l;
    }

    //并查集 find (路径压缩版)
    private static int find(int[] p, int x) {
        if (x != p[x])
            p[x] = find(p, p[x]);
        return p[x];
    }

    //并查集 union
    private static void union(int[] p, int x, int y){
        int rx = find(p, x);
        int ry = find(p, y);
        p[rx] = ry;
    }

    //埃氏筛质数
    private static List<Integer> aiSai(int n){
        int[] arr = new int[n + 1];
        for (int i = 2; i < n + 1; i++) {
            arr[i] = i;
        }
        int i = 2;
        while (i * i <= n){
            int start = i * 2;
            while (start <= n){
                arr[start] = 0;
                start += i;
            }
            i++;
            while (arr[i] == 0){
                i++;
            }
        }
        List<Integer> list = new ArrayList<>();
        for (int j = 0; j < n + 1; j++) {
            if(arr[j] != 0){
                list.add(j);
            }
        }
        return list;
    }

    //区间查询和单点修改最大值(线段树模版)
    private static void modify(int[] max, int o, int l, int r, int idx, int val){
        if (l == r){
            max[o] = val;
            return;
        }
        int m = (l + r) >> 1;
        if (idx <= m){
            modify(max, o * 2, l, m, idx, val);
        }else {
            modify(max, o * 2 + 1, m + 1, r, idx, val);
        }
        max[o] = Math.max(max[o * 2], max[o * 2 + 1]);
    }
    private static int query(int[] max, int o, int l, int r, int L, int R){
        if (L <= l && r <= R){
            return max[o];
        }
        int m = (l + r) >> 1, res = 0;
        if (L <= m){
            res = query(max, o * 2, l, m, L, R);
        }
        if (R > m){
            res = Math.max(res, query(max, o * 2 + 1, m + 1, r, L, R));
        }
        return res;
    }
}
